#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'
const int maxn = 4;
const int INF = 1e9;
int n = 4, m = 4;
char G[maxn][maxn] = {  //平面图 矩形 默认行为n 列为m
        'A', 'B', '/', 'D',
        'E', 'F', '/', '/',
        'I', 'J', 'K', 'L',
        'M', '/', '/', 'P'
};
int book[maxn][maxn];
int fx[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};//四连通 顺时针方向
struct Node {
    int x, y;

};

Node pre[maxn][maxn];//打印最短路径，指向父（前一个）结点
/**
 * 输出源点从源点开始s(sx,sy) 形成的bfs树，pre[i][j]存储的是g[i][j]的父节点
 * @param sx  源点的横坐标
 * @param sy  源点的纵坐标
 * @return
 */
void bfs(int sx, int sy) {
    queue<Node> Q;      //初始化一个点的空队列
    Q.push({sx, sy});     //把起点{x,y}压入队列
    book[sx][sy] = 1;     //入队即标记防止重复访问
    while (!Q.empty()) {
        Node head = Q.front();//获得队头结点
        int hx = head.x;
        int hy = head.y;

        for (int i = 0; i < 4; i++) {
            int nx = hx + fx[i][0];//相邻的四连通点的x新坐标
            int ny = hy + fx[i][1];//相邻的四连通点的y新坐标
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue; //检查位置的有效性
            if (G[nx][ny] == '/' || book[nx][ny] == 1)continue;//避免重复访问

            Q.push({nx, ny});//扩张的点再次入队

            pre[nx][ny].x = hx;
            pre[nx][ny].y = hy;

            book[nx][ny] = 1;//入队即标记防止重复访问
        }
        Q.pop();//出队，删除头结点
    }

}


int main() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pre[i][j].x = -1;
            pre[i][j].y = -1;
        }
    }
    int sx = 0, sy = 0, ex = n - 1, ey = m - 1;//A->P
    bfs(sx, sy);//
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << "(" << pre[i][j].x << "," << pre[i][j].y << ")";

        }
        cout << endl;

    }


    while (true) {
        cout << G[ex][ey] << "<-";
        int px = pre[ex][ey].x;
        int py = pre[ex][ey].y;
        if (px == -1 && py == -1)break;
        ex = px;
        ey = py;
    }

    return 0;
}
